def test():
	def testBinTree():
		tree1 = CompleteBinTreeByLink()
		# seq = list(chr(x+65) for x in range(0, 26))
		seq = list(x for x in range(1, 16))
		tree1.buildFromSeq(seq)
		draw1 = DrawTreeByLink(tree1)
		tree1.append(*(16,17))
		draw1.updateDrawing('append')
		tree1.deleteAndMove()
		draw1.updateDrawing('delete')
		tree1.deleteAndMove(ID = 3)
		draw1.updateDrawing('delete', ID = 3)
		tree1.deleteAndMove(fromID = 6, toID = 14)
		draw1.updateDrawing('delete', fromID = 6, toID = 14)

	def testNormalTree():
		tree1 = CompleteBinTreeByLink()
		seq1 = list(x for x in range(1, 16))
		tree1.buildFromSeq(seq1)
		draw1 = DrawTreeByLink(tree1)

		tree2 = CompleteBinTreeByLink()
		seq2 = list(chr(x+65) for x in range(0, 10))
		tree2.buildFromSeq(seq2)
		draw2 = DrawTreeByLink(tree2)	

		# tree1.insert(13, 30, 'x')
		# draw1.updateDrawing('insert')
		# tree2.insert(6, 31, 'y', ndxInSib = 0)
		# draw2.updateDrawing('insert', insertID = 31)

		tree1.moveToTree(6, tree2, 8)
		draw1.updateDrawing('redraw')
		draw2.updateDrawing('redraw')

		# tree1.insert(11, 32, 'z', ndxInSib = 0)
		# draw1.updateDrawing('insert', insertID = 32)
		# tree1.deleteDown(deleteID = 5)
		# draw1.updateDrawing('deleteDown', lastDeletedIDs = tree1.lastDeletedIDs)

	def testExpTree():
		tree = ExpressionTree()
		expr = '((1-2-4/5*(1/3))+(2+4+3*5)*5)/7'
		# ((1+2-4/5*(1/3))+(2+4+3*5)*5)/7
		# 1,2,+,4,5,/,1,3,/,*,-,2,4,+,3,5,*,+,5,*,+,7,/
		# expr = '1+2*3'
		tree.buildFromExpr(expr)
		draw = DrawTreeByLink(tree)
		draw.updateDrawing('redraw')
		value = tree.evaluate(tree._root)
		print(value)

	def testHeapTree():
		htree = HeapTree()
		# htree.buildFromRandom(10)
		seq = [3, 17, 7, 12, 19, 5, 15, 2, 18, 6]
		htree.buildFromSeq(seq)
		htree.minSort(htree._root)
		draw = DrawTreeByList(htree)
		htree.heapAppend(4)
		draw.updateDrawing('redraw')
		sortedSeq = []
		while htree.size != 0:
			sortedSeq.append(htree.headExtract())
		print(sortedSeq)

	def testBSTree():
		bsTree = BinSearchTree()
		seq = [7, 15, 6, 19, 18, 9, 8, 10, 17, 1, 6, 0, 15, 16, 12]
		seq = [x for x in range(20, 0, -1)]
		bsTree.buildFromSeq(seq)
		bsTree.deleteValue(17)
		bsTree.deleteValue(19)
		seq = bsTree.genSortedSeq()
		print(seq)

	def testAVLTree():
		avlTree = AVLTree()
		# seq = [2, 15, 6, 19, 18, 9, 8, 10, 17, 1, 6, 0, 15, 16, 12]
		seq = [x*2 for x in range(10)]
		avlTree.buildFromSeq(seq)
		avlTree.reshapeAVL()
		draw2 = DrawTreeByLink(avlTree)
		for x in range(21, 29):
			avlTree.insertNodeAVL(x)
		for x in range(-10, 0):
			avlTree.insertNodeAVL(x)
		draw2.updateDrawing('redraw')
		# avlTree.deleteValue(-3)
		# draw2.updateDrawing('redraw')
		for x in range(-3, 3):
			avlTree.deleteValue(x)
			draw2.updateDrawing('redraw')

	def testBMTree():
		btree = BMTree()
		for x in range(13):
			btree.insertValue(x*2)
		draw = DrawTreeByLink(btree)
		btree.insertValue(3)
		draw.updateDrawing('redraw')
		btree.insertValue(5)
		draw.updateDrawing('redraw')

		# print(btree)

	# testBinTree()
	# testNormalTree()
	# testExpTree()
	# testHeapTree()
	# testBSTree()
	# testAVLTree()
	# testBMTree()

	def testRBTree():
		rbTree = RBTree()
		# seq = [randint(0,100) for x in range(23)]
		# seq = [18, 9, 8, 2, 15, 6, 19]
		# seq = [2, 6, 19, 16, 10, 22, 18,17]
		seq = [56, 79, 35, 64, 46, 85, 53, 94, 27, 25, 4, 45, 91, 100, 98, 80, 97, 83, 9, 62, 48, 96, 24]
		seq2 = [163, 118, 147, 164, 119, 117, 121, 158, 126, 165, 196, 191, 163, 177, 109, 187, 135, 172, 164, 139]
		seq += seq2
		for x in seq:
			rbTree.insertValue(x)
		draw1 = DrawTreeByLink(rbTree)
		# # rbTree.insert(17)
		rbTree.deleteValue(45)
		rbTree.deleteValue(46)
		rbTree.deleteValue(9)
		rbTree.deleteValue(24)
		rbTree.deleteValue(35)
		rbTree.deleteValue(53)
		rbTree.deleteValue(4)
		draw1.updateDrawing('redraw')
		rbTree.deleteValue(119)
		draw1.updateDrawing('redraw')
		rbTree.deleteValue(121)
		rbTree.deleteValue(126)
		rbTree.deleteValue(27)
		draw1.updateDrawing('redraw')

	def testRankRBTree():
		rrbTree = RankRBTree() 
		# seq = [56, 79, 35, 64, 46, 85, 53, 94, 27, 25]
		seq = [56, 79, 35, 64, 46, 85, 53, 94, 27, 25, 4, 45, 91, 100, 98, 80, 97, 83, 9, 62, 48, 96, 24]
		# seq2 = [163, 118, 147, 164, 119, 117, 121, 158, 126, 165, 196, 191, 163, 177, 109, 187, 135, 172, 164, 139]
		# seq += seq2
		for x in seq:
			rrbTree.insertValue(x)
		draw1 = DrawTreeByLink(rrbTree)
		# rrbTree.insertValue(4)
		# rrbTree._getSize(rrbTree._root)
		# rrbTree._initRank()
		# print(rrbTree._getRank(45))
		rrbTree.deleteValue(53)
		rrbTree.deleteValue(64)
		draw1.updateDrawing('redraw')
		rrbTree.deleteValue(79)
		draw1.updateDrawing('redraw')

	def testOptTree():
		from random import uniform
		optTree = OptBinSearchTree()
		N = 13
		p = [uniform(0,1) for x in range(1,N)]
		q = [uniform(0,1) for x in range(0,N)]
		summary = sum(p) + sum(q)
		p = [round(x/summary, 2) for x in p]
		q = [round(x/summary, 2) for x in q]
		p.insert(0, None)
		s = [x for x in range(1,N)]
		optTree.buildFromSeq(s)
		optTree.dynOptimize(p, q)
		optTree.adjustOpt()
		for n in range(N):
			optTree.insertNode(n + 0.5)
		for x in range(N-1):
			optTree.nodeRef[x].content = 'k' + str(optTree.nodeRef[x].content) + ' p:' + str(p[x+1])
		for x in range(N-1, 2*N-1):
			optTree.nodeRef[x].content = 'k' + str(optTree.nodeRef[x].content) + ' q:' + str(q[x-N])
		optTree._updateBFTLink(updateAll = True)
		optTree._updateTreeInfo(updateAll = True)
		draw1 = DrawTreeByLink(optTree)

	testOptTree() 

	def testBMTree():
		btree = BMTree()
		# s = ['A','C','D','E','G','M','P','X','J','K','N','O','R','S','T','U','V','Y','Z']
		# s = ['GMPX','ACDE','JK','NO','RSTUV','YZ']
		# s = ['A','B','C','D','E','F','G','J','K','L','M','N','O','P','Q','R','S','T','U','V','X','Y','Z']
		# random.seed(10000)
		s = [randint(1,100) for x in range(100)]
		s1 = [randint(1,100) for x in range(100)]
		# s = [69, 56, 64, 38, 93, 90, 44, 43, 38, 98, 6, 37, 26, 2, 64, 52, 91, 11, 26, 45, 81, 92, 6, 20, 55, 5, 69, 32, \
		# 	94, 43, 3, 93, 13, 19, 53, 98, 73, 57, 5, 76, 13, 36, 26, 91, 32, 25, 100, 48, 44, 76]
		# s1 = [56, 37, 27, 15, 17, 17, 46, 49, 95, 24, 100, 55, 65, 11, 35, 99, 53, 91, 8, 75, 81, 63, 99, 9, 92, 82, 40, 11, 87, 6, 86,  \
		# 	100, 10, 90, 27, 27, 100, 48, 44, 42, 52, 4, 92, 18, 89, 75, 27, 79, 88, 38]
		for x in s:
			btree.insertValue(x)
		draw = DrawTreeByLink(btree)
		for x in s1:
			btree.deleteValue(x)
		# btree.deleteValue(45)
		# btree.deleteValue(48)
		# btree.deleteValue(37)
		# btree.deleteValue(44)
		# btree.deleteValue(43)
		# draw.updateDrawing('redraw')
		# btree.deleteValue(52)
		draw.updateDrawing('redraw')
		# btree.insertValue('B')
		# draw.updateDrawing('redraw')
		# btree.insertValue("Q")
		# draw.updateDrawing('redraw')
		# btree.insertValue("L")
		# draw.updateDrawing('redraw')
		# btree.insertValue("F")
		# draw.updateDrawing('redraw')
	for i in range(5):
		testBMTree()


	def testBinomialHeap():
		heap1 = BinomialHeap()
		heap2 = BinomialHeap()
		# seq1 = [2,3,4,6,7,8,5,6]
		seq2 = [randint(1,30) for x in range(11)]
		seq1 = [4, 7, 14, 14, 21, 37, 4, 29, 8, 5, 26, 2, 15, 30]
		heap1.buildFromSeq(seq1)
		# draw = DrawHeap(heap1)		
		heap2.buildFromSeq(seq2)
		# draw = DrawHeap(heap2)		
		heap1.unionWith(heap2)
		draw = DrawHeap(heap1)		
		heap1.extractMin()
		draw = DrawHeap(heap1)		
		# print(heap1.min)
		# tree, node = heap1._getNode(26)
		# print(tree._root, node)
		heap1.decreaseKey(29, 1)
		draw = DrawHeap(heap1)		
		heap1.deleteKey(37)
		draw = DrawHeap(heap1)		
		# print(heap1[0].max)

	testBinomialHeap()

	def testFibHeap():
		fHeap = FibHeap()
		seq = [5,2,3,4,5,6,8,99,0,33]
		# seq2 = [randint(1,30) for i in range(8)]
		# seq = [randint(1,30) for i in range(randint(10,25))]
		fHeap.buildFromSeq(seq)
		# draw = DrawHeap(fHeap)
		# fHeap.decreaseKey(33,-33)
		# draw = DrawHeap(fHeap)
		fHeap.extractMin()
		draw = DrawHeap(fHeap)
		fHeap.decreaseKey(8, 0)
		draw = DrawHeap(fHeap)
		fHeap.decreaseKey(6, 3)
		draw = DrawHeap(fHeap)
		fHeap.deleteKey(99)
		draw = DrawHeap(fHeap)
		# fHeap.deleteKey(8)
		# draw = DrawHeap(fHeap)
		# print(fHeap.min)
		# h2 = FibHeap()
		# h2.buildFromSeq(seq2)
		# draw = DrawHeap(h2)
		# h2.extractMin()
		# draw = DrawHeap(h2)
		# fHeap.unionWith(h2)
		# draw = DrawHeap(fHeap)
		# for i in range(4):
		# 	fHeap.extractMin()
		# 	draw = DrawHeap(fHeap)
		# 	print(fHeap.min)